# -*- coding:utf-8 -*-
__author__ = 'gin.chen'


# 二叉树
class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right


class BinaryTree:

    def __init__(self, data=None):
        if data is not None:
            self.it = iter(data)
            self.tree = self.init_bt()

    # @classmethod
    # def blank_init(cls):
    #     return cls()

    def init_bt(self, bt=None):
        try:
            next_data = next(self.it)
            # if
            if next_data is "#":
                return None
            else:
                bt = TreeNode(next_data)
                bt.left = self.init_bt(bt.left)
                bt.right = self.init_bt(bt.right)
            return bt
        except Exception as e:
            print e

    def pre_order_traverse_by_stack(self, bt):
        if bt is not None:
            stack = [bt]
            while len(stack) > 0:
                bt = stack.pop()
                print bt.val,
                if bt.right is not None:
                    stack.append(bt.right)
                if bt.left is not None:
                    stack.append(bt.left)

    def middle_order_traverse_by_stack(self, bt):
        if bt is not None:
            stack = []
            pos = bt
            while pos is not None or len(stack) > 0:
                if pos is not None:
                    stack.append(pos)
                    pos = pos.left
                else:
                    pos = stack.pop()
                    print pos.val,
                    pos = pos.right

    def after_order_traverse_by_stack(self, bt):
        if bt is not None:
            stack = [bt]
            stack2 = []
            while len(stack) > 0:
                bt = stack.pop()
                stack2.append(bt)
                # print bt.val,
                if bt.left is not None:
                    stack.append(bt.left)
                if bt.right is not None:
                    stack.append(bt.right)
            while len(stack2) > 0:
                print stack2.pop().val,

    def pre_order_traverse(self, bt):
        if bt is not None:
            print bt.val,
            self.pre_order_traverse(bt.left)
            self.pre_order_traverse(bt.right)

    def middle_order_traverse(self, bt):
        if bt is not None:
            self.middle_order_traverse(bt.left)
            print bt.val,
            self.middle_order_traverse(bt.right)

    def after_order_traverse(self, bt):
        if bt is not None:
            self.after_order_traverse(bt.left)
            self.after_order_traverse(bt.right)
            print bt.val,

    def level_traverse(self, bt):

        if not bt:
            return
        # print "Print binary tree by level"
        queue = [bt]
        last = bt
        level = 1
        # print "Level " + str(level) + ': '
        while queue:
            bt = queue.pop(0)
            print bt.val,
            if bt.left:
                nlast = bt.left
                queue.append(bt.left)
            if bt.right:
                nlast = bt.right
                queue.append(bt.right)
            if bt == last and queue:
                last = nlast
                level += 1
                # print '\n'
                # print "Level " + str(level) + ": "

    def printTrave(self):
        print "先序遍历: "
        self.pre_order_traverse(self.tree)
        print '\n'
        self.pre_order_traverse_by_stack(self.tree)
        print '\n'
        print "中序遍历: "
        self.middle_order_traverse(self.tree)
        print '\n'
        self.middle_order_traverse_by_stack(self.tree)
        print '\n'
        print "后序遍历: "
        self.after_order_traverse(self.tree)
        print '\n'
        self.after_order_traverse_by_stack(self.tree)
        print '\n'
        print "层次遍历: "
        self.level_traverse(self.tree)


if __name__ == '__main__':
    # data = input("Please input the node value: ")
    # data_list = list("abd#g###ce##fh###")
    data_list = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
    BinaryTree(data_list).printTrave()

